如何用Python递归地思考问题？
【Python数据科学社区】↓
这是 Python数据科学的第 54 篇原创文章
【作者】：xiaoyu
【介绍】：一个半路转行的数据挖掘工程师
【知乎专栏】：https://zhuanlan.zhihu.com/pypcfx
全文3345字 | 阅读需要5分钟
递归是一个很经典的算法，在实际中应用广泛，也是面试中常常会提到的问题。本文就递归算法介绍如何在Python中实现递归的思想，以及递归在Python中使用时的一些注意事项，希望能够对使用Python的朋友提供一些帮助。
1通俗地认识递归
为了更通俗的解释递归，我们通过一个简单的例子来说明。圣诞节到了，圣诞老人要给4个小朋友发礼物。每年过节，圣诞老人都会将礼物一家接一家的送，直到送完。这个过程我们可以通过一个简单的循环来实现，如下：
houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]
def deliver_presents_iteratively():
for house in houses:
print("Delivering presents to", house)
循环执行结果如下：
>>> deliver_presents_iteratively()
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house但是今天圣诞老人觉得太累了，想偷个懒，不想自己一个个的送了。突然间脑袋灵光一闪，他想出了一个办法，可以让孩子们帮他来送礼物，并通过孩子们传递下去。这样不但可以让孩子们感受过节的气氛，自己也可以省一部分力气，简直是两全其美啊。于是乎，圣诞老人开始执行这个策略。
1. 先指定一名小朋友，然后将所有的工作交给他。
2. 根据小朋友所负责的房子数量，来分配他们各自的职位和工作内容。
如果房子数量>1，那么他就是一个管理者，并可以再指定两名小朋友来帮他完成他负责的工作。
如果房子数量=1，那么他就是一个工作人员，他必须将礼物送到指定的房子。
这就是一个典型的递归算法结构。核心的思想就是：如果眼下的问题是一个最简单的问题，那么解决它。如果不是最简单的，那就将问题划分，直到成为最简单问题，再运用同样的策略进行解决。
用Python语言来实现以上递归思想可以这样做：
houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]
# 每次函数调用都代表一个小朋友负责的工作
def deliver_presents_recursively(houses):
# 工作人员通过送礼物，来执行工作
if len(houses) == 1:
house = houses[0]
print("Delivering presents to", house)
# 管理者通过分配工作，来执行所负责的工作
else:
mid = len(houses) // 2
first_half = houses[:mid]
second_half = houses[mid:]
# 将工作划分给另外两个小朋友
deliver_presents_recursively(first_half)
deliver_presents_recursively(second_half)
执行结果如下：
>>> deliver_presents_recursively(houses)
Delivering presents to Eric's house
Delivering presents to Kenny's house
Delivering presents to Kyle's house
Delivering presents to Stan's house
2Python中的递归函数
相信通过以上的举例，大家对递归已经有了一个初步的认识。现在来正式地介绍一下递归函数的定义。如果一个函数直接或者间接地调用函数本身，那么就是递归函数。
这意味着，函数将不断的调用本身并重复函数的内容，直到达到某个条件才返回一个结果。所有的递归函数都有着同样的结构，这个结构由两部分组成：基础部分，递归部分。
为了更好地说明这个结构，我们举一个例子说明，来写一个递归函数计算n的阶层（n！）：
1. 递归部分：将原始问题（n！）分解为最简单并且相同的小问题。通过将n！分解我们看到这个更小且相同的问题就是每次与比自己小于1的数字相乘（n*(n-1)!）：
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1
n! = n x (n−1)!2. 基础部分：上面的递归部分将大的问题分解为一个个相同的小问题，但是肯定不会无限制的递归下去。我们需要找到一个不能继续往下递归的停止条件，也就是基础部分。通过不断分解n！我们发现最后到达1的时候不能再继续递归了，因此，1！就是我们最后的基础部分。
n! = n x (n−1)!
n! = n x (n−1) x (n−2)!
n! = n x (n−1) x (n−2) x (n−3)!
⋅
⋅
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2!
n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!
知道了递归结构中的这两个部分，我们在Python中来实现n！的递归算法：
def factorial_recursive(n):
# 基础部分: 1! = 1
if n == 1:
return 1
# 递归部分: n! = n * (n-1)!
else:
return n * factorial_recursive(n-1)
执行结构如下：
> factorial_recursive(5)
120
虽然知道如何写出一个递归算法了，但是对于程序背后的原理我们也是要了解的。程序背后的底层场景是：每次递归调用会添加一个桟帧（包含它的执行内容）到栈，不断添加直到达到了基础部分的停止条件，然后栈再依次解开每个调用并返回它的结果，可以参考下图。
3状态维持
当处理递归函数时，每次递归调用都有自己的执行上下文，即每次递归调用之间的状态都是独立的。当我们想每次递归的时候都更新一个状态，并得到最后的更新结果，那该怎么办呢？为了维持递归中想要维持的状态，我们有两种方法可以使用：
将状态嵌入到每一次的递归调用中作为参数。
将状态设置为全局变量。
我们使用一个例子来说明上面提到的两种方法。比如，我们要使用递归计算1+2+3...+10，这里我们必须要维持的状态就是累积和。
将状态作为参数递归调用
下面我们使用第一种方法，即将状态嵌入每次递归中维持状态，来实现上面例子。
def sum_recursive(current_number, accumulated_sum):
# 基础部分
# 返回最后状态
if current_number == 11:
return accumulated_sum
# 递归部分
# 将状态嵌入到每次递归调用中
else:
return sum_recursive(current_number + 1, accumulated_sum + current_number)
执行结果如下：
# 传递初始状态
> sum_recursive(1, 0)
55
设置状态为全局变量
下面我们使用第二种方法，即设置全局变量，来实现上面例子。
# 全局变量
current_number = 1
accumulated_sum = 0
def sum_recursive():
global current_number
global accumulated_sum
# 基础部分
if current_number == 11:
return accumulated_sum
# 递归部分
else:
accumulated_sum = accumulated_sum + current_number
current_number = current_number + 1
return sum_recursive()
执行结果如下：
> sum_recursive()
55
通常我更喜欢使用将状态作为函数参数的方法实现递归，因为全局变量是有一些弊端的。
4Python中的递归数据结构
如果一个数据结构可以分解成一个个和自己一样的更小的版本，那么这个数据结构也可以是递归的。列表就是一个递归数据结构的典型例子。下面，让我们就来验证一下。现在有一个空的列表，并且可以在列表上使用的唯一操作规定如下：
# 返回一个新的列表，返回结果为在input_list表头添加一个新元素
def attach_head(element, input_list):
return [element] + input_list
通过使用空列表和attach_head操作，我们就可以生成任何列表了。例如，我们想生成 [1，46，-31，"hello"]：
attach_head(1, # Will return [1, 46, -31, "hello"]
attach_head(46, # Will return [46, -31, "hello"]
attach_head(-31, # Will return [-31, "hello"]
attach_head("hello", [])))) # Will return ["hello"]
上面实现过程如下：
递归数据结构和递归函数可以一起配合使用。通常我们可以将递归数据结构作为递归函数的参数来实现递归。因为我们知道了递归数据结构是递归的，我们就可以轻易地将递归数据结构拆分为一个个更小并且相同小的问题，然后通过递归进行解决。
下面就是一个将列表作为递归函数参数的例子，递归部分是利用了列表的切片操作，不断切分列表为更小的部分，停止条件就是直到列表为空。
def list_sum_recursive(input_list):
# 基础部分
if input_list == []:
return 0
# 递归部分
else:
head = input_list[0]
smaller_list = input_list[1:]
return head + list_sum_recursive(smaller_list)
执行结构如下：
> list_sum_recursive([1, 2, 3])
6
但列表并不是唯一的递归数据结构。其它的还包括集合，树，字典等。
5递归的注意事项
在我们用Python实现递归的过程中，也有一些地方需要注意。
递归效率问题
我们通过举一个例子来说明，比如我们要使用递归实现斐波那契数列。
递归部分： Fn = Fn-1 + Fn-2
基础部分： F0 = 0 and F1 = 1
在Python中实现递归：
def fibonacci_recursive(n):
print("Calculating F", "(", n, ")", sep="", end=", ")
# 基础部分
if n == 0:
return 0
elif n == 1:
return 1
# 递归部分
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
执行结果如下：
>>> fibonacci_recursive(5)
Calculating F(5),
Calculating F(4),
Calculating F(3),
Calculating F(2),
Calculating F(1),
Calculating F(0),
Calculating F(1),
Calculating F(2),
Calculating F(1),
Calculating F(0),
Calculating F(3),
Calculating F(2),
Calculating F(1),
Calculating F(0),
Calculating F(1),
5
我们发现计算过程中有很多重复计算的部分，这样会严重影响我们递归实现的效率。那该如何优化一下呢？
Python中有一个强大的装饰器：lru_cache，它主要是用来做缓存，能把相对耗时的函数结果进行保存，避免传入相同的参数重复计算。LRU全称为Least Recently Used，相信好多朋友都知道这个算法，这里不进行详细讲解了。
下面我们来看一下加入装饰器lru_cache之后效果如何。
from functools import lru_cache
def fibonacci_recursive(n):
print("Calculating F", "(", n, ")", sep="", end=", ")
# 基础部分
if n == 0:
return 0
elif n == 1:
return 1
# 递归部分
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)执行结果如下：
>>> fibonacci_recursive(5)
Calculating F(5),
Calculating F(4),
Calculating F(3),
Calculating F(2),
Calculating F(1),
Calculating F(0),
5
从结果发现一些重复的计算过程已经消失，这样就节省了很多时间，提升了递归的运行效率。但要注意的是：lru_cache是通过使用一个字典来缓存结果的，因此函数的位置和关键字参数（字典中的keys）必须是散列的。
递归深度问题
Python不支持tail-call elimination（尾调用消除）。因此，如果我们使用了更多的桟帧，并且超过了默认的调用栈的深度，那么你将会引起栈溢出的问题。
我们通过getrecursionlimit观察默认的递归深度限制，默认为3000。所以，这个我们需要注意一下。
> import sys
> sys.getrecursionlimit()
3000
同样还有，Python的可变数据结构不支持结构化共享，如果把它们当成了不可变数据结构，那么这将会对我们的空间和GC（垃圾回收）效率造成很不好的影响。因为这样做会不必要地复制很多可变对象作为结尾，下面举了一个简单的例子说明。
> input_list = [1, 2, 3]
> head = input_list[0]
> tail = input_list[1:]
> print("head --", head)
head -- 1
> print("tail --", tail)
tail -- [2, 3]
tail是通过复制创建的，因此，如果我们在很大的列表上递归地重复用这个复制操作，那么就会对我们的空间和GC效率产生坏的影响。
https://realpython.com/python-thinking-recursively/
每日推荐阅读书籍